home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / hash / Hash_CreateEntry.c < prev    next >
C/C++ Source or Header  |  1989-11-30  |  5KB  |  200 lines
  1. /* 
  2.  * Hash_CreateEntry.c --
  3.  *
  4.  *    Source code for the Hash_CreateEntry library procedure.
  5.  *
  6.  * Copyright 1988 Regents of the University of California
  7.  * Permission to use, copy, modify, and distribute this
  8.  * software and its documentation for any purpose and without
  9.  * fee is hereby granted, provided that the above copyright
  10.  * notice appear in all copies.  The University of California
  11.  * makes no representations about the suitability of this
  12.  * software for any purpose.  It is provided "as is" without
  13.  * express or implied warranty.
  14.  */
  15.  
  16. #ifndef lint
  17. static char rcsid[] = "$Header: /sprite/src/lib/c/hash/RCS/Hash_CreateEntry.c,v 1.3 88/07/28 17:57:23 ouster Exp Locker: mgbaker $ SPRITE (Berkeley)";
  18. #endif not lint
  19.  
  20. #include <hash.h>
  21. #include <list.h>
  22. #include <stdlib.h>
  23. #include <string.h>
  24.  
  25. /*
  26.  * Utility procedures defined in other files:
  27.  */
  28.  
  29. extern Hash_Entry *    HashChainSearch();
  30. extern int        Hash();
  31.  
  32. /* 
  33.  * The following defines the ratio of # entries to # buckets
  34.  * at which we rebuild the table to make it larger.
  35.  */
  36.  
  37. static rebuildLimit = 3;
  38.  
  39. /*
  40.  *---------------------------------------------------------
  41.  *
  42.  * RebuildTable --
  43.  *    This local routine makes a new hash table that
  44.  *    is larger than the old one.
  45.  *
  46.  * Results:    
  47.  *     None.
  48.  *
  49.  * Side Effects:
  50.  *    The entire hash table is moved, so any bucket numbers
  51.  *    from the old table are invalid.
  52.  *
  53.  *---------------------------------------------------------
  54.  */
  55.  
  56. static void
  57. RebuildTable(tablePtr)
  58.     Hash_Table     *tablePtr;        /* Table to be enlarged. */
  59. {
  60.     int          oldSize;
  61.     int          bucket;
  62.     List_Links         *oldBucketPtr;
  63.     register Hash_Entry  *hashEntryPtr;
  64.     register List_Links     *oldHashList;
  65.  
  66.     oldBucketPtr = tablePtr->bucketPtr;
  67.     oldSize = tablePtr->size;
  68.  
  69.     /* 
  70.      * Build a new table 4 times as large as the old one. 
  71.      */
  72.  
  73.     Hash_InitTable(tablePtr, tablePtr->size * 4, tablePtr->keyType);
  74.  
  75.     for (oldHashList = oldBucketPtr; oldSize > 0; oldSize--, oldHashList++) {
  76.     while (!List_IsEmpty(oldHashList)) {
  77.         hashEntryPtr = (Hash_Entry *) List_First(oldHashList);
  78.         List_Remove((List_Links *) hashEntryPtr);
  79.         switch (tablePtr->keyType) {
  80.         case HASH_STRING_KEYS:
  81.             bucket = Hash(tablePtr, (Address) hashEntryPtr->key.name);
  82.             break;
  83.         case HASH_ONE_WORD_KEYS:
  84.             bucket = Hash(tablePtr, (Address) hashEntryPtr->key.ptr);
  85.             break;
  86.         default:
  87.             bucket = Hash(tablePtr, (Address) hashEntryPtr->key.words);
  88.             break;
  89.         }
  90.         List_Insert((List_Links *) hashEntryPtr, 
  91.         LIST_ATFRONT(&(tablePtr->bucketPtr[bucket])));
  92.         tablePtr->numEntries++;
  93.     }
  94.     }
  95.  
  96.     free((Address) oldBucketPtr);
  97. }
  98.  
  99. /*
  100.  *---------------------------------------------------------
  101.  *
  102.  * Hash_CreateEntry --
  103.  *
  104.  *    Searches a hash table for an entry corresponding to
  105.  *    key.  If no entry is found, then one is created.
  106.  *
  107.  * Results:
  108.  *    The return value is a pointer to the entry.  If *newPtr
  109.  *    isn't NULL, then *newPtr is filled in with TRUE if a
  110.  *    new entry was created, and FALSE if an entry already existed
  111.  *    with the given key.
  112.  *
  113.  * Side Effects:
  114.  *    Memory may be allocated, and the hash buckets may be modified.
  115.  *---------------------------------------------------------
  116.  */
  117.  
  118. Hash_Entry *
  119. Hash_CreateEntry(tablePtr, key, newPtr)
  120.     register Hash_Table *tablePtr;    /* Hash table to search. */
  121.     Address key;            /* A hash key. */
  122.     Boolean *newPtr;            /* Filled in with TRUE if new entry
  123.                          * created, FALSE otherwise. */
  124. {
  125.     register Hash_Entry *hashEntryPtr;
  126.     register int     *hashKeyPtr;
  127.     register int     *keyPtr;
  128.     List_Links         *hashList;
  129.  
  130.     keyPtr = (int *) key;
  131.  
  132.     hashList = &(tablePtr->bucketPtr[Hash(tablePtr, (Address) keyPtr)]);
  133.     hashEntryPtr = HashChainSearch(tablePtr, (Address) keyPtr, hashList);
  134.  
  135.     if (hashEntryPtr != (Hash_Entry *) NULL) {
  136.     if (newPtr != NULL) {
  137.         *newPtr = FALSE;
  138.     }
  139.         return hashEntryPtr;
  140.     }
  141.  
  142.     /* 
  143.      * The desired entry isn't there.  Before allocating a new entry,
  144.      * see if we're overloading the buckets.  If so, then make a
  145.      * bigger table.
  146.      */
  147.  
  148.     if (tablePtr->numEntries >= rebuildLimit * tablePtr->size) {
  149.     RebuildTable(tablePtr);
  150.     hashList = &(tablePtr->bucketPtr[Hash(tablePtr, (Address) keyPtr)]);
  151.     }
  152.     tablePtr->numEntries += 1;
  153.  
  154.     /*
  155.      * Not there, we have to allocate.  If the string is longer
  156.      * than 3 bytes, then we have to allocate extra space in the
  157.      * entry.
  158.      */
  159.  
  160.     switch (tablePtr->keyType) {
  161.     case HASH_STRING_KEYS:
  162.         hashEntryPtr = (Hash_Entry *) malloc((unsigned)
  163.             (sizeof(Hash_Entry) + strlen((char *) keyPtr) - 3));
  164.         strcpy(hashEntryPtr->key.name, (char *) keyPtr);
  165.         break;
  166.     case HASH_ONE_WORD_KEYS:
  167.         hashEntryPtr = (Hash_Entry *) malloc(sizeof(Hash_Entry));
  168.         hashEntryPtr->key.ptr = (Address) keyPtr;
  169.         break;
  170.     case 2:
  171.         hashEntryPtr = 
  172.         (Hash_Entry *) malloc(sizeof(Hash_Entry) + sizeof(int));
  173.         hashKeyPtr = hashEntryPtr->key.words;
  174.         *hashKeyPtr++ = *keyPtr++;
  175.         *hashKeyPtr = *keyPtr;
  176.         break;
  177.     default: {
  178.         register     n;
  179.  
  180.         n = tablePtr->keyType;
  181.         hashEntryPtr = (Hash_Entry *) 
  182.             malloc((unsigned) (sizeof(Hash_Entry)
  183.             + (n - 1) * sizeof(int)));
  184.         hashKeyPtr = hashEntryPtr->key.words;
  185.         do { 
  186.         *hashKeyPtr++ = *keyPtr++; 
  187.         } while (--n);
  188.         break;
  189.     }
  190.     }
  191.  
  192.     hashEntryPtr->clientData = (ClientData) NULL;
  193.     List_Insert((List_Links *) hashEntryPtr, LIST_ATFRONT(hashList));
  194.  
  195.     if (newPtr != NULL) {
  196.     *newPtr = TRUE;
  197.     }
  198.     return hashEntryPtr;
  199. }
  200.